package com.fps.webshop.question.question0001_0099;

import java.util.ArrayList;
import java.util.List;

/**
 * 4. 寻找两个正序数组的中位数
 * 
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * 
 * 示例 1：
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 * 
 * 示例 2：
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.50000
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 * 
 * 示例 3：
 * 输入：nums1 = [0,0], nums2 = [0,0]
 * 输出：0.00000
 * 
 * 示例 4：
 * 输入：nums1 = [], nums2 = [1]
 * 输出：1.00000
 * 
 * 示例 5：
 * 输入：nums1 = [2], nums2 = []
 * 输出：2.00000
 * 
 * 提示：
 * 		nums1.length == m
 * 		nums2.length == n
 * 		0 <= m <= 1000
 * 		0 <= n <= 1000
 * 		1 <= m + n <= 2000
 * 		-106 <= nums1[i], nums2[i] <= 106
 * 
 * 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
 */
public class Question004 {
	
	/**
	 * 第一次提交，使用了重建数组的方法，但时间复杂度并不理想，或许可以使用二分查找
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		3 ms	39.8 MB	Java	2021/08/04 16:40
	 */
	public double findMedianSortedArrays(int[] nums1, int[] nums2) {
		List<Integer> list = new ArrayList<Integer>();
		int index1 = 0;
		int index2 = 0;
		int length = nums1.length+nums2.length;
		for(int i=0;i<length;i++) {
			if(index1<nums1.length&&index2<nums2.length) {
				if(nums1[index1]<nums2[index2]) {
					list.add(nums1[index1]);
					index1++;
				}else {
					list.add(nums2[index2]);
					index2++;
				}
			}else if(index1>=nums1.length&&index2<nums2.length) {
				list.add(nums2[index2]);
				index2++;
			}else if(index1<nums1.length&&index2>=nums2.length) {
				list.add(nums1[index1]);
				index1++;
			}else if(index1>=nums1.length&&index2>=nums2.length) {
				break;
			}
		}
		
		
		int num = list.size()/2;
		if(list.size()%2==0) {
			return (double)(list.get(num-1)+list.get(num))/2;
		}else {
			return (double)(list.get(num));
		}
		
    }
	/*
	 * public static void main(String[] args) { String s = "pwwkew";
	 * System.out.print(lengthOfLongestSubstring(s)); }
	 */
}
